#include<vector>
using namespace std;

class Solution {
private:
    void mergeSort(vector<pair<int,int>>& vec,int start,int end, vector<int>& res) {
        if (start >= end - 1) return;
        int mid = start + (end - start) / 2;
        mergeSort(vec, start, mid, res);
        mergeSort(vec, mid, end, res);
        vector<pair<int, int>> tmp(end - start);
        int first = start, second = mid;
        int cnt = 0;
        for (int i = 0; i < end - start; ++i) {
            if (second>=end||(first< mid &&vec[first].second <= vec[second].second)) {
                res[vec[first].first] += cnt;
                tmp[i] = vec[first++];
            }
            else {
                tmp[i] = vec[second++];
                ++cnt;
            }
        }
        for (int i = 0; i < tmp.size(); ++i)
            vec[i + start] = tmp[i];
    }


public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<pair<int, int>>vec;
        for (int i = 0; i < nums.size(); ++i) {
            vec.emplace_back(i, nums[i]);
        }
        vector<int>res(nums.size());
        mergeSort(vec, 0, nums.size(), res);
        return res;
    }
};

//int main() {
//    vector<int> nums = { 5,2,6,1 };
//    Solution sol;
//    sol.countSmaller(nums);
//}